1. יש 2 רשימות מקושרות. לבדוק האם יש איבר משותף. למצוא אותו לכתוב קוד. בסיבוכיות זמן ומקום מינימאליות.
2. לבנות class לשמירת נתונים בצורה key->value. עם מתודות set,get,reset. reset אמור להגדיר כל האיברים לאותו ערך תוך О(1). גם set,get אמורים לעבוד בО(1). מתודה init(n) בO(n)
תשובות
הוסף תשובה
|
לצפיה בתשובות
מרץ 2022
יש להגדיר משתנים כמו timestamp ו-default_value. כל פעם כשמוסיפים איבר חדש יש לקדם את timestamp ולשמור את ערכו יחד עם האיבר. ב-reset יש לשנות default_value ולשמור timestamp שלו, זה O(1). ב-get יש לבדוק timestamp של איבר, להשוות אותו עם timestamp של default_value ולהחזיר את החדש יותר.
שאלו שאלה על 9 מטבעות. 8 זהות במשקלן ואחת שוקלת יותר. מה הדרך הנכונה ביותר לשקילה עם מאזניים על מנת למצוא את המטבע השונה במינימום שקילות.
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2022
צריך מסקימום 3 שקילות (רק שקילה אחת במקרה הטוב):
שקילה ראשונה: מטבעות 1-4 על כף מאזניים אחת, מטבעות 5-8 על כף שנייה. אם המאזניים מאוזנות אז מטבע מספר 9 הוא הכבד יותר, אם לא ממשיכים:
שקילה שנייה: לוקחים את הרביעיה הכבדה יותר ומפצלים אותה לשניים-שניים על המאזניים.
שקילה שלישית: לוקחים את זוג המטבעות הכבד יותר ומפצלים אותו למטבעות בודדים על המאזניים, וכך נגלה את המטבע הכבד ביותר.
מרץ 2022
אפשר לעשות תמיד ב2 שקילות.
לוקחים את מטבע 1-3 ואת מטבע 4-6, אם הן מאוזנות אז המטבע המזויף נמצא ב7-9. בסוף עושים עוד שקילה אחת עם ה3 מטבעות שנשאר. אם מאוזן המטבע שנותר בחוץ הוא המזויף. ככה תמיד מוצאים את התשובה ב2 שקילות.
- שאלות בנושא של מערכות הפעלה - לדוגמא מקביליות של חוטים,מנעולים וסנכרון בין תהליכים.
- שאלות בנושאים כללים - מציאת ערך של האיבר החסר במערך, ושל שני איברים חסרים במערך - מערך שמכיל N-1 איברים מתוך טווח של 1...N
תשובות
הוסף תשובה
|
לצפיה בתשובות
נובמבר 2021
לגבי מספר אחד פיתרון קל זה סכום סדרה חשבונית ואז לחסר את איברי המערך
לגבי שני מספרים מה שעולה לי זה N! ואז לחלק את כל איברי המערך ולעשות את מה שעשינו עם מספר 1.
אז יש לנו 2 משוואת עם 2 נעלמים ( לא בטוח שזה הכי אופטימלי)
ינואר 2022
יש פתרון כללי (לגבי נעלם אחד, לגבי שני נעלמים, 3 נעלמים וכו').
מגדירים וקטור בגודל N+1 (+1 כי הטווח 1..N מתחיל מ1 ולא מאפס) ומאתחלים את כל הוקטור בשקר (FALSE). עוברים על המערך בלולאה ומכניסים אמת (TRUE) לתוך התאים שהאינדקס שלהם נמצא במערך המספרים:
v[arr[i] = true;
לאחר מכן מריצים לולאה נוספת שרצה על הוקטור ומדפיסים את התאים שיש בהם שקר.
יש לך 4 אנשים צריכים לעבור את הנהר מצד לצד ו יש להם רק מנורה אחת והם צריכים להשתמש בה ו רק שניים יכולים לעבור כל פעם. האיש 1 יכול לעבור לצד השני ב 10 דקות ו השני ב 7 דקות ו השלישי ב 2 דקות והאחרון ה 1 דקה . מה הוא הזמן הכי קצר כדי לעביר את כל האנשים לצד השני של הנהר
תשובות
הוסף תשובה
|
לצפיה בתשובות
יוני 2021
להשתמש ב איש האחרון (כי הוא עובר בדקה) ו לתת לו את המנורה וכל פעם הוא עובר עם אחד מ האנשים לצד השני וחוזר עד פעם לקחת את השני ו את השלישי
יולי 2021
1 ו-2 עוברים ראשונים (2 דקות)
1 חוזר לבד (3 דקות)
1 יורד, 10 ו-7 עוברים יחד (13 דקות)
שניהם יורדים, 2 עולה וחוזר להביא את 1 (15 דקות)
2 ו-1 חוזרים (17 דקות)
יולי 2021
- השניים המהירים יוצאים ראשון (2 ד׳)
- המהיר חוזר (1 ד׳)
- שני האיטיים יוצאים (10 ד׳)
- המהיר השני חוזר (2 ד׳)
- שני המהירים יוצאים (2 ד׳)
סכ״ה 17 ד׳
אוקטובר 2021
השניים הכי מהירים יוצאים ראשונים - 2 דק
ההכי מהיר חוזר - 1 דק
שני האיטיים יוצאים עם המנורה - 10 דק
2 חוזר עם המנורה - 2 דק
שני המהירים יוצאים שוב יחד - 2 דק
סכה 17 דק
ראיון לתפקיד 
